#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;

/*
 *在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。

例子：

[1,3,4,2,5]

1左边比1小的数，没有；

3左边比3小的数，1；

4左边比4小的数，1、3；

2左边比2小的数，1；

5左边比5小的数，1、3、4、2；

所以小和为1+1+3+1+1+3+4+2=16

要求时间复杂度O(NlogN)，空间复杂度O(N)
 *
 *
 * */
//todo 明天记得看
typedef long long LL;
const int N = 1e5 + 10;
int nums[N];
int temp[N];

//long long是因为结果可能爆int
LL merge(int a[], int l, int mid, int r) {
    int i = l, j = mid + 1, k = 0;
    LL res = 0;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            res += (r - j + 1) * a[i];
            temp[k++] = a[i++];
        } else temp[k++] = a[j++];
    }
    while (i <= mid) temp[k++] = a[i++];
    while (j <= r) temp[k++] = a[j++];
    for (i = l, k = 0; i <= r; i++)
        a[i] = temp[k++];
    return res;
}

LL getSmallSum(int a[], int l, int r) {
    if (l == r) return 0;
    int mid = (l + r) / 2;
    LL L = getSmallSum(a, l, mid), R = getSmallSum(a, mid + 1, r);
    LL c = merge(a, l, mid, r);
    return L + R + c;
}

int main__add_more() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> nums[i];
    cout << getSmallSum(nums, 0, n - 1) << endl;
    return 0;
}
//___________________________

int merge_(vector<int> nums, int low, int mid, int high) {
    vector<int> left(nums.begin() + low, nums.begin() + mid + 1);
    vector<int> right(nums.begin() + mid + 1, nums.begin() + high + 1);
    int i = 0;
    int j = 0;
    int index = low;

    int res = 0;
    //寻找 左边比右边小的元素
    // 暂且咱们从小到大
    while (i < left.size() && j < right.size()) {
        if (left[i] <= right[j]) {
            //  1 2 3 4 5
            // 4>1 则5>1
            res += (right.size() - j) * left[i];//todo
            nums[index++] = right[i++];

        } else {

            nums[index++] = left[j++];
        }
    }

    while (i < left.size()) {
        nums[index++] = left[i++];
    }

    while (j < right.size()) {
        nums[index++] = right[j++];
    }

    return res;
}

//这个返回值 搞得我有点懵逼
int merge_sort(vector<int> &nums, int low, int high) {
    if (low >= high) return 0;
    int mid = low + (high - low) / 2;
    int a = merge_sort(nums, low, mid);
    int b = merge_sort(nums, mid + 1, high);
    int c = merge_(nums, low, mid, high);
    return a + b + c;
}

void test_aaa() {
    vector<int> aa = {1, 2, 3, 4, 5};
    int a = merge_sort(aa, 0, aa.size() - 1);
    cout << a;
}